package selfLearn.theList.tree;

import java.util.Map;

/**
 * 描述:
 *
 * @Package: selfLearn.theList.tree
 * @ClassName: BinaryTree
 * @Author: 陈威
 * @CreateTime: 2022/2/16 16:37
 * @Description:
 */
public class BinaryTree<Key extends Comparable<Key>, Value> {
    private Node root;
    private int N;

    private class Node {
        private Key key;
        private Value value;
        private Node left;
        private Node right;

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }


    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    public Node put(Node target, Key key, Value value) {
        //如果target目标子树为空，则返回创建的叶子节点
        if (target == null) {
            N++;
            return new Node(key, value, null, null);
        }
        //根节点不为空 则判断target节点的key与key的大小
        int flag = key.compareTo(target.key);
        //如果key大于target节点的key则右递归找右子节点的右子树
        if (flag > 0) {
            target.right = put(target.right, key, value);
        }//如果key小于target节点的key则左递归找左子节点的左子树
        else if (flag < 0) {
            target.left = put(target.left, key, value);
        } else {
            //如果key等于x结点的键，则替换x结点的值为value即可
            target.value = value;
        }
        return target;
    }

    public Value get(Key key){
        return get(root,key);
    }

    public Value get(Node root,Key key){
        if (root==null){
            return null;
        }
        Node tartget=root;
        int flag=key.compareTo(tartget.key);
        if(flag>0){
            return get(tartget.right,key);
        }else if(flag<0){
            return get(tartget.left,key);
        }else {
            return tartget.value;
        }
    }

    public void delete(Key key){
        root=delete(root,key);
    }
    public Node delete(Node root,Key key){
        if (root==null){
            return null;
        }
        //判断当前节点key与目标节点是否匹配
        int flag=key.compareTo(root.key);
        //目标节点key大于当前节点key 则继续右递归右子树进行查询
        if(flag>0){
            delete(root.right,key);
        }//目标节点key小于当前节点key 则继续左递归左子树进行查询
        else if(flag<0){
            delete(root.left,key);
        }else {
            //这里的root的key与目标key已经相等 root节点就是要找的目标删除节点
            //找到要删除的节点后 要考虑该节点在删除后他的左子节点跟右子节点怎么处理
            //可以根据规律判断 最适合替代被删除的节点的目标节点一定是他的右子树的最小左子树

            if(root.right==null){
                return root.left;
            }

            if(root.left==null){
                return root.right;
            }

            //寻找最小左子树节点
            Node minNode=root.right;
            while (minNode.left!=null){
                minNode=minNode.left;
            }
            //删除最小左子树节点
            Node delMinNode=root.right;
            while (delMinNode.left!=null){
                if(delMinNode.left.left==null){
                    delMinNode.left=null;
                }else {
                    delMinNode=delMinNode.left;
                }
            }

            //最后 将最小左子树的右子树换为待删除节点的右子树
            minNode.right=root.right;
            minNode.left=root.left;
            root=minNode;
            N--;
        }
        return root;
    }
}
